package ai.zixing.mashibing.basic_class.class10;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 图的拓扑排序
 */
public class Code03_TopologySort {

    public static List<Node> sortedTopology(Graph graph) {
        // key: 某一个 node
        // value: 剩余的入度
        HashMap<Node, Integer> inMap = new HashMap<>();
        // 入度为 0 的点，添加到队列
        Queue<Node> zeroInQueue = new LinkedList<>();
        // 获取图中的点集
        for (Node node : graph.nodes.values()) {
            // 初始化点集
            inMap.put(node, node.in);
            if (node.in == 0) {
                zeroInQueue.add(node);
            }
        }
        // 排序的结果
        List<Node> result = new ArrayList<>();
        while (!zeroInQueue.isEmpty()) {
            Node cur = zeroInQueue.poll();
            result.add(cur);
            // 找到所有邻居节点，处理边
            for (Node next : cur.nexts) {
                // 边处理之后，邻居的入度 - 1
                inMap.put(next, inMap.get(next) - 1);
                if (inMap.get(next) == 0) {
                    zeroInQueue.add(next);
                }
            }
        }
        return result;

    }
}
